翻訳と辞書 Words near each other ・ Induced consumption ・ Induced demand ・ Induced gamma emission ・ Induced gas flotation ・ Induced gravity ・ Induced high electron mobility transistor ・ Induced homomorphism ・ Induced homomorphism (algebraic topology) ・ Induced homomorphism (fundamental group) ・ Induced homomorphism (quotient group) ・ Induced innovation ・ Induced menopause ・ Induced metric ・ Induced movement ・ Induced ovulation (animals) ・ Induced path ・ Induced pluripotent stem cell ・ Induced pluripotent stem-cell therapy ・ Induced polarization ・ Induced radioactivity ・ Induced representation ・ Induced seismicity ・ Induced seismicity in Basel ・ Induced stem cells ・ Induced subgraph isomorphism problem ・ Induced thymic epithelial cells ・ Induced topology ・ Induced-charge electrokinetics ・ Induced-self antigen ・ Inducement (disambiguation) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Induced path ： ウィキペディア英語版 Induced path In the mathematical area of graph theory, an induced path in an undirected graph ''G'' is a path that is an induced subgraph of ''G''. That is, it is a sequence of vertices in ''G'' such that each two adjacent vertices in the sequence are connected by an edge in ''G'', and each two nonadjacent vertices in the sequence are not connected by any edge in ''G''. An induced path is sometimes called a snake, and the problem of finding long induced paths in hypercube graphs is known as the snake-in-the-box problem. Similarly, an induced cycle is a cycle that is an induced subgraph of ''G''; induced cycles are also called chordless cycles or (when the length of the cycle is four or more) holes. An antihole is a hole in the complement of ''G'', i.e., an antihole is a complement of a hole. The length of the longest induced path in a graph has sometimes been called the detour number of the graph;〔.〕 for sparse graphs, having bounded detour number is equivalent to having bounded tree-depth.〔, Proposition 6.4, p. 122.〕 The induced path number of a graph ''G'' is the smallest number of induced paths into which the vertices of the graph may be partitioned,〔.〕 and the closely related path cover number of ''G'' is the smallest number of induced paths that together include all vertices of ''G''.〔.〕 The girth of a graph is the length of its shortest cycle, but this cycle must be an induced cycle as any chord could be used to produce a shorter cycle; for similar reasons the odd girth of a graph is also the length of its shortest odd induced cycle. == Example == The illustration shows a cube, a graph with eight vertices and twelve edges, and an induced path of length four in this graph. A straightforward case analysis shows that there can be no longer induced path in the cube, although it has an induced cycle of length six. The problem of finding the longest induced path or cycle in a hypercube, first posed by , is known as the snake-in-the-box problem, and it has been studied extensively due to its applications in coding theory and engineering. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Induced path」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.